#include <bits/stdc++.h>
using namespace std;

/*
3027. 人员站位的方案数 II
已解答
困难
相关标签
premium lock icon
相关企业
提示
给你一个  n x 2 的二维数组 points ，它表示二维平面上的一些点坐标，其中 points[i] = [xi, yi] 。

我们定义 x 轴的正方向为 右 （x 轴递增的方向），x 轴的负方向为 左 （x 轴递减的方向）。类似的，我们定义 y 轴的正方向为 上 （y 轴递增的方向），y 轴的负方向为 下 （y 轴递减的方向）。

你需要安排这 n 个人的站位，这 n 个人中包括 Alice 和 Bob 。你需要确保每个点处 恰好 有 一个 人。同时，Alice 想跟 Bob 单独玩耍，所以 Alice 会以 Alice 的坐标为 左上角 ，Bob 的坐标为 右下角 建立一个矩形的围栏（注意，围栏可能 不 包含任何区域，也就是说围栏可能是一条线段）。如果围栏的 内部 或者 边缘 上有任何其他人，Alice 都会难过。

请你在确保 Alice 不会 难过的前提下，返回 Alice 和 Bob 可以选择的 点对 数目。

注意，Alice 建立的围栏必须确保 Alice 的位置是矩形的左上角，Bob 的位置是矩形的右下角。比方说，以 (1, 1) ，(1, 3) ，(3, 1) 和 (3, 3) 为矩形的四个角，给定下图的两个输入，Alice 都不能建立围栏，原因如下：

图一中，Alice 在 (3, 3) 且 Bob 在 (1, 1) ，Alice 的位置不是左上角且 Bob 的位置不是右下角。
图二中，Alice 在 (1, 3) 且 Bob 在 (1, 1) ，Bob 的位置不是在围栏的右下角。

 

示例 1：



输入：points = [[1,1],[2,2],[3,3]]
输出：0
解释：没有办法可以让 Alice 的围栏以 Alice 的位置为左上角且 Bob 的位置为右下角。所以我们返回 0 。
示例 2：



输入：points = [[6,2],[4,4],[2,6]]
输出：2
解释：总共有 2 种方案安排 Alice 和 Bob 的位置，使得 Alice 不会难过：
- Alice 站在 (4, 4) ，Bob 站在 (6, 2) 。
- Alice 站在 (2, 6) ，Bob 站在 (4, 4) 。
不能安排 Alice 站在 (2, 6) 且 Bob 站在 (6, 2) ，因为站在 (4, 4) 的人处于围栏内。
示例 3：



输入：points = [[3,1],[1,3],[1,1]]
输出：2
解释：总共有 2 种方案安排 Alice 和 Bob 的位置，使得 Alice 不会难过：
- Alice 站在 (1, 1) ，Bob 站在 (3, 1) 。
- Alice 站在 (1, 3) ，Bob 站在 (1, 1) 。
不能安排 Alice 站在 (1, 3) 且 Bob 站在 (3, 1) ，因为站在 (1, 1) 的人处于围栏内。
注意围栏是可以不包含任何面积的，上图中第一和第二个围栏都是合法的。
 

提示：

2 <= n <= 1000
points[i].length == 2
-109 <= points[i][0], points[i][1] <= 109
points[i] 点对两两不同。
*/

// 法一
class Solution {
public:
    int numberOfPairs(vector<vector<int>>& points) {
        // 依旧比较左上角
        // sort 按x坐标升序排列，x相同时按y坐标降序排列
        sort(points.begin(), points.end(), [](const vector<int>& a, const vector<int>& b) {
            if (a[0] == b[0])   return a[1] > b[1];
            return a[0] < b[0];
        });
        // x相同时y降序，保证同x点中y大的在前，便于后续y条件判断

        int ans = 0, n = points.size();

        // 固定Alice pos
        for (int i = 0; i < n; i++) {
            int a_y = points[i][1];     // Alice y.pos
            int max_y_diff = INT_MIN;   // Alice 和 Bob 之间所有点的最大y
            // 寻找Bob pos（j为Bob的索引，j > i保证x_j >= x_i）
            for (int j = i + 1; j < n; j++) {
                int b_y = points[j][1];
                // Bob 是否 在Alice的右下角
                if (b_y > a_y) {
                    // 不满足就continue了 要更新中间最大y
                    // max_y_diff = max(max_y_diff, b_y); // 不更新max_y_between，因为该点不会在矩形内
                    continue;
                }

                // 找 Alice 和 Bob 之间 所有点的最大y < b_y
                if (max_y_diff < b_y)   ans++;
                max_y_diff = max(max_y_diff, b_y);
            }
        }
        return ans;
    }
};

// 法二
// 常数级优化 加了剪枝
class Solution {
public:
    int numberOfPairs(vector<vector<int>>& points) {
        // 排序策略：x升序，x相同则y降序
        // 保证j > i时x_j >= x_i，只需关注y坐标条件
        sort(points.begin(), points.end(), [](const vector<int>& a, const vector<int>& b) {
            return a[0] != b[0] ? a[0] < b[0] : a[1] > b[1];
        });
        
        int ans = 0;
        int n = points.size();
        
        for (int i = 0; i < n; ++i) {
            int alice_y = points[i][1];
            int max_y = INT_MIN;  // 记录i到j之间、y<=alice_y的最大y值
            
            // 内层循环仅处理y_j <= alice_y的点，减少无效判断
            for (int j = i + 1; j < n; ++j) {
                int bob_y = points[j][1];
                if (bob_y > alice_y) continue;  // 不满足Bob在右下角的y条件
                
                // 核心判断：中间无点落在[y_bob, alice_y]区间内
                if (bob_y > max_y) {
                    ans++;
                    max_y = bob_y;  // 更新最大值，确保后续点不会被中间点阻挡
                }
            }
        }
        
        return ans;
    }
};

// 法三
// ranges支持似乎更佳
class Solution {
public:
    // 时间复杂度 O(n²)，排序占 O(n log n)，核心逻辑为两层循环
    int numberOfPairs(vector<vector<int>>& points) {
        // 排序策略：使用ranges::sort按投影排序
        // 投影为pair(p[0], -p[1])，等价于：
        // 1. 先按x坐标升序排列（p[0]小的在前）
        // 2. 若x相同，按y坐标降序排列（-p[1]小即p[1]大的在前）
        // 作用：确保j > i时，points[j][0] >= points[i][0]（满足Alice在Bob左侧的x条件）
        //      x相同时y大的在前，避免同x点间无效对（同x时只有y小的可作为Bob）
        ranges::sort(points, {}, [](auto& p) { return pair(p[0], -p[1]); });

        int n = points.size();
        int ans = 0;  // 有效点对数量
        
        // 外层循环：固定Alice的位置（i为Alice的索引）
        for (int i = 0; i < n; i++) {
            int y1 = points[i][1];  // Alice的y坐标
            int max_y = INT_MIN;    // 记录i到j之间、满足条件的点的最大y值（初始为最小值）

            // 内层循环：寻找Bob的位置（j > i确保x_j >= x_i，满足x条件）
            for (int j = i + 1; j < n; j++) {
                int y2 = points[j][1];  // Bob的y坐标

                // 核心条件：
                // 1. y2 <= y1：Bob的y坐标 <= Alice的y坐标（满足Bob在右下角的y条件）
                // 2. y2 > max_y：i到j之间所有点的y值均小于当前Bob的y值（确保矩形内无其他点）
                if (y2 <= y1 && y2 > max_y) {
                    max_y = y2;  // 更新最大y值，后续Bob需更大y值才有效（避免中间点阻挡）
                    ans++;       // 找到有效点对，计数+1
                }
            }
        }

        return ans;
    }
};